#pragma once
#include "common.h"
void InsertSort(vector<int>& nums, int begin, int step) {
    int n = nums.size();
    for (int i = begin; i < n; i += step) {
        int num = nums[i];
        for (int j = i - step; j >= 0; j -= step) {
            if (nums[j] > num) {
                nums[j + step] = nums[j];
                nums[j] = num;
            }
            else {
                break;
            }
        }
    }
}
void ShellSort(vector<int>& nums) {
    int n = nums.size();
    int step = n;
    while (step > 1) {
        step = step / 3 + 1;
        for (int i = 0; i < step; ++i) {
            InsertSort(nums, i, step);
        }
    }
}